//题目链接https://leetcode.cn/problems/validate-binary-search-tree/

// 递归
//单纯的递归并不能判断，因为从上到下递归需要考虑边界问题，不考虑的话就会单纯的只判断子树根节点与当前节点的大小关系造成错误。
//判断左子树时，其下边界不变，上边界变为根节点，右子树的上边界不变，下边界变为根节点
class Solution {
public:
	//其中的边界就是做一个限定，保证当前子树的所有节点满足条件
    bool helper(TreeNode* root, long long lower, long long upper) {
        if (root == nullptr) {
            return true;
        }
        if (root -> val <= lower || root -> val >= upper) {
            return false;
        }
        return helper(root -> left, lower, root -> val) && helper(root -> right, root -> val, upper);
    }
    bool isValidBST(TreeNode* root) {
        return helper(root, LONG_MIN, LONG_MAX);
    }
};
//中序解决1
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if(root == nullptr) return true;
        vector<int> ivec;
        inorder(root,ivec);
        for(vector<int>::iterator it = ivec.begin();it!=ivec.end()-1;++it){
            if(*(it+1)<=*it)   return false;
        }
        return true;
    }
    void inorder(TreeNode* root,vector<int>& vec){
        if(root == nullptr) return;
        inorder(root->left,vec);
        vec.push_back(root->val);
        inorder(root->right,vec);
    }
};

//中序解决2
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> st;
        long long flag= (long long)INT_MIN - 1;
        //二叉搜索树中序遍历是升序
        while(!st.empty() || root){
            while(root){
                st.push(root);
                root = root->left;
            }
            root = st.top();
            st.pop();

            if(flag >= root->val)  return false;
            
            flag = root->val;
            root = root->right;
        }
        return true;
    }
};

//递归